This invention relates generally to data encoding in solid state storage devices (SSDs). Methods and apparatus are provided for encoding data and recording the encoded data in s-level solid state storage, where s f 2 represents the number of different values, or levels, that can be assumed by the fundamental storage unit, or “cell”, of the solid state memory.
Solid-state storage is memory which uses electronic circuitry, typically in integrated circuits, for storing data rather than conventional magnetic or optical media like disks and tapes. Solid state storage devices such as flash memory devices are currently revolutionizing the data storage landscape. These devices are more rugged than conventional storage devices due to the absence of moving parts, and offer exceptional bandwidth, significant savings in power consumption, and random I/O (input/output) performance that is orders of magnitude better than hard disk drives (HDDs).
Conventional storage devices such as HDDs record binary data. That is, the fundamental storage unit in these devices holds only one bit of information. Volatile solid state memory technologies such as DRAMs (dynamic random access memories) also record binary data, the fundamental storage cell in such memories being capable of assuming only two levels (s=2), and hence recording only binary values. In other types of SSD, however, the storage cells can assume more than two levels (s>2). For example, flash memory and phase change memory (PCM), two important non-volatile memory technologies, allow multi-level recording. NOR flash memories, for instance, can store 4 levels, i.e., 2 bits, per cell. Multi-level cell (MLC) NAND flash memory chips that can store 4 bits of data per single flash cell using 43 nm process technology are currently available. The PCM technology is expected to supplant flash memory technologies when process technologies below 10 nm are required. Although commercially available PCM chips currently store only one bit per cell, storage of 4 bits per cell in PCM chips has already been experimentally demonstrated.
Due to the success of solid state memories such as flash and PCM in consumer products like digital cameras and music players, these memory technologies are currently being considered for enterprise storage. Error performance, which is always a key issue for data storage devices, becomes increasingly important as these technologies move into the enterprise space. While conventional storage devices like HDDs have an ECC (error correction code) overhead of about 10% to 15%, the ECC overhead in commercially available flash memories is only about 2.5% to 5%. Efficiency is therefore critical for EC coding schemes in these devices.
In SSDs, the storage is organized into storage areas, or blocks, each of which contains a set of storage locations to which data can be written. EC coding is performed in SSDs by adding redundancy at the write-unit level, i.e. within each data write location. Flash memory, for example, contains data write locations known as “pages”. Each page contains a plurality of sectors, but write operations are usually performed on a page basis. An EC code is computed for the input data written to each flash page, or each sector within a page, and the EC code is recorded in that page, or sector, with the input data. This coding allows recovery from errors within individual data pages. Linear codes such as RS (Reed-Solomon) and BCH (Bose-Chaudhuri-Hocquenghem) codes have been employed for this so-called “one-level” EC coding. “Long” one-level codes, where the encoding is performed on a page basis (i.e. one codeword per page) make the best use of available page redundancy and therefore give the best error performance, but these schemes are extremely complex to implement and require high power consumption if the page size and the desired error correction capability is large. The complexity associated with these codes depends on the size of the finite field (the Galois field (GF)) in which the encoding and decoding arithmetic is performed. (In the following, the set of all N-tuples with elements from the Galois field with q elements, denoted by GF(q), is a vector space denoted by GF(q)N). For example, long one-level codes for two different page sizes with a payload of 2 KiB and 4 KiB have been designed. It was assumed that the available ECC overhead (redundancy) of the long one-level codes with payloads of 2 KiB and 4 KiB was 56 bytes and 120 bytes, respectively. The best 2 KiB one-level RS code (where 2 KiB is the page size) can correct up to 20 randomly selected 11-bit symbols per page but requires GF(211) arithmetic both for encoding and decoding. The best 4 KiB one-level RS code can correct up to 40 randomly selected 12-bit symbols in a page but requires GF(212) arithmetic for encoding and decoding. Moreover, the best 2 KiB one-level BCH code, which can correct up to 29 randomly selected bits per page, requires GF(2) arithmetic for encoding but GF(215) arithmetic for decoding. The best 4 KiB one-level BCH code, which can correct up to 60 randomly selected bits per page, requires GF(2) arithmetic for encoding but GF(216) arithmetic for decoding. Because of the inordinate complexity of these long codes, “short” one-level codes, where multiple shorter codewords are contained in a single page, are used in practice, sacrificing error performance for practicality of implementation.
U.S. Pat. No. 7,047,478 B2 discloses a one-level coding system for multi-level cell memory in which the operating mode is switchable from a mode in which all available storage levels are used to a mode in which less than all levels are used. To accommodate this, the coding scheme employs a q-ary alphabet (i.e. the codewords are formed of symbols which can take q different values) where q is equal to the number of available levels s of the multilevel cells.
As described in “Integrated Interleaving—A Novel ECC Architecture,” M. Hassner, et al., IEEE Trans. on Magn., vol. 37, no. 2, pp. 773-775, March 2001, and U.S. Pat. Nos. 5,946,328, 5,942,005 and 7,231,578 B2, two-level coding schemes using interleaved RS codes have been employed in HDDs. These systems are based on the generalized concatenated codes described, for example, in: E. L. Blokh and V. V. Zyablov, “Generalized concatenated codes,” Plenum Publishing Corporation, pp. 218-222, 1976 (translated from Problemy Peredachi Informatsii, vol. 10, No. 3, pp. 45-50, July-September, 1974); and J. Maucher et al., “On the Equivalence of Generalized Concatenated Codes and Generalized Error Location Codes”, IEEE Trans. on Information Theory, vol. 46, no. 2, March 2000. The two-level RS coding scheme of Hassner et al. referenced above uses first and second RS codes, denoted by C1 and C2 respectively, where the second RS code is a sub-code of the first RS code. A set of M first (C1) codewords is generated such that a linear combination of these M codewords is a second (C2) codeword. In particular, a number B f 1 of weighted sums of the M C1 codewords in the aforementioned set are respective C2 codewords of the second RS code. The weighting coefficients for these weighted sums are defined by a Vandermonde matrix. In addition, the coding scheme is subject to the limitation M<q, i.e. the number of C1 codewords M in the aforementioned set is less than the total number of Galois field elements q. For example, in the case of binary linear codes over GF(q=2) the condition M<2 applies for integrated interleaving codes, i.e., M=1 and so the family of integrated interleaving codes defined by Hassner et al. does not contain binary two-level codes. The use of multiple RS codewords, interleaved over a sector, in this scheme increases the robustness to burst errors in the HDD channel. RS codes are well suited to this and are widely favoured in general. This may be due in part to the ease of performance evaluation since the weight distributions of RS codes are known. Implementation complexity also compares favourably with BCH codes as illustrated above, decoding in particular being significantly less complex for RS codes.
Two-level RS coding has also been adopted for DRAMs as discussed in “Reliable Memories with Subline Accesses”, Junsheng Han et al., ISIT2007, Nice, France, June 24-June 29, pp. 2531-2535, and US Patent Application No. 2008/0168329 A1. The two-level RS coding is based on the integrated interleaving scheme of Hassner et al. referenced above though code design details and decoding algorithms are unspecified.